//
// Created by daiyizheng on 2022/3/27.
//
#include <vector>

using namespace std;
/**
对于一棵深度小于 5 的树，可以用一组三位十进制整数来表示。

对于每个整数：

百位上的数字表示这个节点的深度 D，1 <= D <= 4。
十位上的数字表示这个节点在当前层所在的位置 P， 1 <= P <= 8。位置编号与一棵满二叉树的位置编号相同。
个位上的数字表示这个节点的权值 V，0 <= V <= 9。
给定一个包含三位整数的升序数组，表示一棵深度小于 5 的二叉树，
请你返回从根到所有叶子结点的路径之和。
样例 1:
输入: [113, 215, 221]
输出: 12
解释:
这棵树形状如下:
    3
   / \
  5   1
路径和 = (3 + 5) + (3 + 1) = 12.


样例 2:
输入: [113, 221]
输出: 4
解释:
这棵树形状如下:
    3
     \
      1
路径和 = (3 + 1) = 4.
 */
int ans = 0;
void dfs(int i, vector<int>& tree, int sum) {
    if (tree[i] == -1) return;

    sum += tree[i];
    if ((i + 1 >= 8) || (tree[2 * i + 1] == -1 && tree[2 * i + 2] == -1)) {
        ans += sum;
        return;
    }

    dfs(2 * i + 1, tree, sum);
    dfs(2 * i + 2, tree, sum);
}

int pathSum(vector<int>& nums) {
    vector<int> nodes(15, -1);
  // 二叉树数组构建
    for(int num:nums){
        int bai = num/100;
        int shi = num%100/10;
        int ge = num%10;
        int index = (1 << (bai - 1)) - 1 + shi - 1;
        nodes[index] = ge;
    }

    //遍历二叉树

    dfs(0, nodes, 0);
    return ans;
}